'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-04 10:39:28
'''
'''
32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"


以状态dp[i+1]标识s[i]结尾的有效括号的长度。dp长度设为len(s)+1为的是边界检查。
状态转移方程为值为')'的状态转移方程为
dp[i+1] = dp[i]+2+dp[i-dp[i]-1]
'''
from typing import List

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp = [0]*(len(s)+1)
        re = 0
        for i, v in enumerate(s):
            if v == ')':
                if i-dp[i]-1>-1 and s[i - dp[i]-1] == '(':
                    dp[i+1] = dp[i]+2+dp[i - dp[i]-1]
                    re = max(re, dp[i+1])
        return re
        


if __name__ == "__main__":
    solution = Solution()
    s = ")()())"
    print(solution.longestValidParentheses(s))